#include "./leetcode.h"
#include "treenode.h"
/*
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal
*/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

typedef struct
{
    int key;
    int val;
    UT_hash_handle hh;
} HashTable;

HashTable* hashTable;

void insertHash(int key, int val)
{
    HashTable* rec = malloc(sizeof(HashTable));
    rec->key = key;
    rec->val = val;
    HASH_ADD_INT(hashTable, key, rec);
}

int queryHash(int key)
{
    HashTable* res;
    HASH_FIND_INT(hashTable, &key, res);
    return res->val;
}

struct TreeNode* getTree(int* inorder, int* postorder, int inLeft, int inRight, int postLeft, int postRight)
{
    if (inLeft > inRight)
    {
        return NULL;
    }

    int index = queryHash(postorder[postRight]);
    int length = index - inLeft;
    struct TreeNode* node = malloc(sizeof(struct TreeNode));
    node->val = postorder[postRight];

    node->left = getTree(inorder, postorder, inLeft, index - 1, postLeft, postLeft + length - 1);
    node->right = getTree(inorder, postorder, index + 1, inRight, postLeft + length, postRight - 1);

    return node;
}

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize)
{

    hashTable = NULL;
    /*
    在 C 语言中，全局变量会被自动初始化为零值（NULL 对于指针类型）。因此，如果 `hashTable` 是一个全局变量，它会被自动初始化为 NULL，而不需要手动初始化。
    但是，如果 `hashTable` 不是全局变量，而是定义在函数内部或是作为参数传递给函数的局部变量，那么它就不会被自动初始化为 NULL。在这种情况下，需要手动将 `hashTable` 初始化为 NULL，以确保在第一次使用它之前是一个有效的空指针。
    综上所述，为了避免未初始化的指针可能导致的未定义行为，建议在定义 `hashTable` 变量时将其初始化为 NULL，即使它是一个全局变量。
*/
    for (int i = 0; i < inorderSize; i++)
    {
        insertHash(inorder[i], i);
    }

    return getTree(inorder, postorder, 0, inorderSize - 1, 0, postorderSize - 1);

}